package q238_productExceptSelf;

public class Solution {
    /*
    此题要求求出除自身之外的数组乘积
    并且要求时间复杂度o(n) 空间o(1)
    并且不能够使用除法
    因此分析：
    乘积 = 当前数左边的乘积 * 当前数右边的乘积
     */
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int p = 1, q = 1;
        // 第一个循环能够记录 对于每个数的位置 其 左侧所有的数乘积
        for (int i = 0; i < nums.length; i++) {
            res[i] = p;
            p = p * nums[i];
        }

        // 第二个循环则对应的 将每个数乘以 其 右侧所有的数乘积
        for (int i = nums.length - 1; i >= 0; i--) {
            q = q * nums[i];
            res[i - 1] =  res[i - 1] * q;
        }

        return res;
    }
}
